home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / hzip.com / HUFFDEC.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1991-01-08  |  3.3 KB  |  144 lines
  1. //////////////////////////////////////////////////////
  2. // huffdec.cpp: huffman decoder methods huffdec.cpp
  3. // Copyright (c) 1991 Azarona Software
  4. // All rights reserved. 
  5. //////////////////////////////////////////////////////
  6.  
  7. #include <string.h>
  8. #include "huffdec.h"
  9.  
  10. int huff_decoder::connect(FILE *f, long locn)
  11. {
  12.   static char signature[] = "HZIP 1.0";
  13.   fin = f;
  14.  
  15.   fseek(f, locn, SEEK_SET);
  16.   fread(signature, 8, 1, f);
  17.   if (strcmp(signature, "HZIP 1.0")) return 0;
  18.   build_tree(ftell(f));
  19.   text_locn = ftell(f);
  20.   reset();
  21.   return 1;
  22. }
  23.  
  24. void huff_decoder::reset(void)
  25. // Resets cbit, which when decompressing will cause the
  26. // next data byte to be read.
  27. {
  28.    cbit = -1;
  29. }
  30.  
  31. void huff_decoder::reset(long locn)
  32. {
  33.   fseek(fin, locn, SEEK_SET);
  34.   reset();
  35. }
  36.  
  37. int huff_decoder::get_bits(int nbits)
  38. // Get next n bits from bitstream
  39. {
  40.   int i, word = 0;
  41.   for (i = 0; i<nbits; i++) {
  42.       if (cbit < 0) {
  43.          cbyte = get_input_char();
  44.          if (cbyte == -1) return -1;
  45.          cbit = 7;
  46.       }
  47.       word <<= 1; word &= 0xfffe;
  48.       word |= ((cbyte >> cbit--) & 0x0001);
  49.   }
  50.   return word;
  51. }
  52.  
  53. int huff_decoder::get_next_char(void)
  54. // Gets the next uncompressed character by walking the
  55. // huffman binary coding tree. Returns -1 when all the 
  56. // uncompressed bytes have been returned.
  57. {
  58.   int r = 0; /* Root starts at zero */
  59.  
  60.   while (1) {
  61.     if (cbit < 0) {
  62.        cbyte = get_input_char();
  63.        if (cbyte == -1) return -1;
  64.        cbit = 7;
  65.     }
  66.     if ((cbyte >> cbit--) & 0x0001)
  67.        r = tree[r].left; 
  68.        else r = tree[r].right;
  69.     if (r & 0x100) return r & 0xff; // Return symbol
  70.   }
  71. }
  72.  
  73. void huff_decoder::build_tree(long codes_locn)
  74. // Assumes codes are perfect
  75. {
  76.   int sym;
  77.   char bit, nbits;
  78.   char *code_lens;
  79.   unsigned *codes, bits;
  80.   int next_avail_node;
  81.   tree_node *cn;
  82.  
  83.   next_avail_node = 0;
  84.  
  85.   fseek(fin, codes_locn, SEEK_SET);
  86.  
  87.   fread(&num_symbols, sizeof(int), 1, fin);
  88.  
  89.   code_lens = new char[num_symbols];
  90.   codes = new unsigned[num_symbols];
  91.  
  92.   fread(codes, sizeof(unsigned), num_symbols, fin);
  93.   fread(code_lens, sizeof(char), num_symbols, fin);
  94.  
  95.   tree = new tree_node[num_symbols];
  96.  
  97.   for (sym = 0; sym < num_symbols; sym++) {
  98.       tree[sym].left = tree[sym].right = -1;
  99.   } 
  100.  
  101.   for (sym = 0; sym < num_symbols; sym++) {
  102.     nbits = code_lens[sym];
  103.     bits = codes[sym];
  104.     cn = tree;
  105.     while(nbits) {
  106.       bit = (bits & 0x8000) != 0;
  107.       if (nbits == 1) {
  108.          if (bit) {
  109.             // if (cn->left != -1) printf("oops!\n");
  110.             cn->left = num_symbols + sym;
  111.          }
  112.          else {
  113.             // if (cn->right != -1) printf("oops!\n");
  114.             cn->right = num_symbols + sym;
  115.          }
  116.       }
  117.       else {
  118.         if (bit) {
  119.            if (cn->left == -1) {
  120.               cn->left = ++next_avail_node;
  121.               cn = tree + next_avail_node;
  122.            }
  123.            else {
  124.               cn = tree + cn->left;
  125.            }
  126.         }
  127.         else {
  128.            if (cn->right == -1) {
  129.               cn->right = ++next_avail_node;
  130.               cn = tree + next_avail_node;
  131.            }
  132.            else {
  133.              cn = tree + cn->right;
  134.            }
  135.         }
  136.       }
  137.       bits <<= 1;
  138.       nbits--;
  139.     }
  140.   }
  141.   delete codes;
  142.   delete code_lens;
  143. }
  144.